Maximum binary tree

Time: O(N); Space: O(N); medium

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

  1. The root is the maximum number in the array.

  2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.

  3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: nums = [3,2,1,6,0,5]

     3
   /    \
  2      1
 / \    /
6   0  5

Output: {TreeNode} [6,3,5,None,2,0,None.None,None,None,1]

    6
 /    \
3      5
 \     /
  2   0
   \
    1

Note:

  • The size of the given array will be in the range [1,1000].

[5]:

class TreeNode(object):
    '''
    Definition for a binary tree node
    '''
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def print_tree(self):
        """
        Print tree content inorder
        """
        if self.left:
            self.left.print_tree()
        print(self.val, end = '')
        if self.right:
            self.right.print_tree()

Auxiliary Tools

[6]:

from graphviz import Graph

class TreeTasks(object):
    def visualize_tree(self, tree):
        def add_nodes_edges(tree, dot=None):
            # Create Graph (not Digraph) object
            if dot is None:
                dot = Graph()
                dot.node(name=str(tree), label=str(tree.val))
            # Add nodes
            if tree.left:
                dot.node(name=str(tree.left), label="."+str(tree.left.val))
                dot.edge(str(tree), str(tree.left))
                dot = add_nodes_edges(tree.left, dot=dot)
            if tree.right:
                dot.node(name=str(tree.right), label=str(tree.right.val)+".")
                dot.edge(str(tree), str(tree.right))
                dot = add_nodes_edges(tree.right, dot=dot)
            return dot
        # Add nodes recursively and create a list of edges
        dot = add_nodes_edges(tree)
        # Visualize the graph
        display(dot)
        return dot

Solution

[7]:

class Solution1(object):
    def constructMaximumBinaryTree(self, nums) -> TreeNode:
        '''
        :type nums: List[int]
        :rtype: TreeNode
        '''
        nodeStack = []
        for num in nums:
            node = TreeNode(num);

            while nodeStack and num > nodeStack[-1].val:
                node.left = nodeStack.pop()

            if nodeStack:
                nodeStack[-1].right = node
            nodeStack.append(node)

        return nodeStack[0]

[8]:

s = Solution1()
nums = [3, 2, 1, 6, 0, 5]
new_tree = s.constructMaximumBinaryTree(nums)
# new_tree.print_tree()    # 321605
t = TreeTasks()
dot = t.visualize_tree(new_tree)
../../_images/topics_tree_0654_maximum_binary_tree_[O(N),O(N),med]_6_0.svg